package algorithm.leetcode.I1to100;

/**
 * 判断一个数独是否合法
 * 注意不是一个解是否合法,输入可能存在空白格子,相当于要实现整个数独回溯解法的isLegal方法
 * 合法数组的充要条件:
 * 1.横行数字不重复
 * 2.纵列数字不重复
 * 3.九个小的3*3区域内数字不重复
 */

public class Q36 {

    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] col = new int[9][9];
        int[][] diag = new int[9][9];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '1';
                    // 小数独
                    // i [0,1,2,3,4,5,6,7,8] -> [0,0,0,3,3,3,6,6,6]
                    // j [0,1,2,3,4,5,6,7,8] -> [0,0,0,1,1,1,2,2,2]
                    // i+j就可以变成下面的方阵
                    //   0 0 0 1 1 1 2 2 2
                    // 0 0 0 0 1 1 1 2 2 2
                    // 0 0 0 0 1 1 1 2 2 2
                    // 0 0 0 0 1 1 1 2 2 2
                    // 3 3 3 3 4 4 4 5 5 5
                    // 3 3 3 3 4 4 4 5 5 5
                    // 3 3 3 3 4 4 4 5 5 5
                    // 6 6 6 6 7 7 7 8 8 8
                    // 6 6 6 6 7 7 7 8 8 8
                    // 6 6 6 6 7 7 7 8 8 8
                    int index_box = (i / 3) * 3 + j / 3;

                    // 这个判重逻辑是:第i个行/列/小数组的数字应该填在rows/col/diag的第i行的对应数字这个位置
                    // 如果这个位置之前填过了(用1标识)说明重复了,直接返回false
                    // 如果这个位置之前没填过(按这个代码数组是用0初始化的)把这个位置填1
                    if (rows[i][num] == 1) return false;
                    else rows[i][num] = 1;

                    if (col[j][num] == 1) return false;
                    else col[j][num] = 1;

                    if (diag[index_box][num] == 1) return false;
                    else diag[index_box][num] = 1;

                }
            }
        }
        return true;
    }

}
